Error Correction Codes (ECCs) are commonly used in communication and storage systems. Various physical phenomena occurring both in communication channels and in storage devices result in noise effects that corrupt the communicated or stored information. Error correction coding schemes can be used for protecting the communicated or stored information against the resulting errors. This is done by encoding the information before transmission through the communication channel or storage in the memory device. The encoding process transforms an information bit sequence into a codeword by adding redundancy to the information. For example, the encoding process may add one or more parity bits to the bit sequence. This redundancy can then be used in order to recover the information from a corrupted codeword through a decoding process. An ECC decoder decodes the corrupted codeword and recovers a bit sequence that should be equal to the original information bit sequence with high probability.
Iterative coding schemes have become very popular in recent years, due to the ability of such codes to achieve near Shannon limit performance at low decoding complexity.
One popular class of iterative codes is Low-Density Parity-Check (LDPC) codes. An LDPC code is a linear binary block code defined by a sparse parity-check matrix H. As shown in FIG. 1, the code can also be defined by a sparse bipartite graph G=(V, C, E) with a set V of N bit nodes (N=13 in FIG. 1), a set C of M check nodes (M=10 in FIG. 1) and a set E (E=38 in FIG. 1) of edges connecting bit nodes to check nodes. The bit nodes correspond to the codeword bits and the check nodes correspond to parity-check constraints on the bits. A bit node is connected by edges to the check nodes in which it participates.
LDPC codes can be decoded using iterative message passing decoding algorithms. These algorithms operate by exchanging messages between bit nodes and check nodes over the edges of the underlying bipartite graph representing the code. The decoder is provided with initial estimates of the codeword bits (based on the communication channel output or based on the read memory content). These initial estimates are refined and improved by imposing the parity-check constraints that the bits should satisfy as a valid codeword. This is done by exchanging information between the bit nodes representing the codeword bits and the check nodes representing parity-check constraints on the codeword bits, using the messages that are passed along the graph edges. Example embodiments of implementation of a LDPC code are described further in U.S. patent application Ser. No. 12/489,576, filed Jun. 23, 2009, and U.S. Provisional Patent Application 61/074,706, which are herein incorporated by reference in their entirety.
The bit estimations conveyed by the messages passed along the graph edges can be expressed in various forms. A common measure for expressing bit estimation is Log-Likelihood Ratio (LLRs), which is defined in the following equation:
                              L          ⁢                                          ⁢          L          ⁢                                          ⁢          R                =                  log          ⁢                                    Pr              (                              v                =                                  0                  ❘                                      current                    ⁢                                                                                  ⁢                    constraints                    ⁢                                                                                  ⁢                    and                    ⁢                                                                                  ⁢                    observations                                                              )                                      Pr              (                              v                =                                  1                  ❘                                      current                    ⁢                                                                                  ⁢                    constraints                    ⁢                                                                                  ⁢                    and                    ⁢                                                                                  ⁢                    observations                                                              )                                                          (        1        )            where the “current constraints and observations” are the various parity-check constraints taken into account in computing the message at hand, and the observations v correspond to the bits participating in these parity checks. Without loss of generality, LLR notation is used throughout the rest of this document. The sign of the LLR provides the bit estimation (i.e., positive LLR corresponds to v=0, and negative LLR corresponds to v=1). The magnitude of the LLR provides the reliability of the estimation (i.e., |LLR|=0 means that the estimation is completely unreliable; and |LLR|=∞ means that the estimation is completely reliable, and the bit value is known).
The messages passed during the decoding operation along the graph edges between bit nodes and check nodes may be extrinsic. An extrinsic message m passed from a node n on edge e may take into account all the values received on edges connected to n other than edge e. In other words, extrinsic messages may be based only on new information.
One example of a message passing decoding algorithm is the belief-propagation (BP) algorithm, which is one of the more common algorithms among this family of algorithms.
Let Pv denote the initial decoder estimation for bit v, based solely on the received or read symbol y, where Pv is a LLR value that may be defined as follows:
                              P          v                =                  log          ⁢                                    Pr              ⁡                              (                                  v                  =                                      0                    ❘                    y                                                  )                                                    Pr              ⁡                              (                                  v                  =                                      1                    ❘                    y                                                  )                                                                        (        2        )            
Let Qv denote the final decoder estimation for bit v, based on the entire received or read sequence y, and assuming that bit v is part of a codeword (i.e., assuming H·v=0 where v (underlined) denotes a vector and v denote a single element of the vector v), then:
                              Q          v                =                  log          ⁢                                    Pr              ⁡                              (                                                      v                    =                                          0                      ❘                                              y                        _                                                                              ,                                                            H                      ·                                              v                        _                                                              =                    0                                                  )                                                    Pr              ⁡                              (                                                      v                    =                                          1                      ❘                                              y                        _                                                                              ,                                                            H                      ·                                              v                        _                                                              =                    0                                                  )                                                                        (        3        )            Let Qvc and Rcv denote a message from bit node v to check node c, and a message from check node c to bit node v, respectively, then a BP-algorithm utilizes the following update rules for computing the messages.
The bit node to check node computation rule is:
                              Q          vc                =                              P            v                    +                                    ∑                                                c                  ′                                ∈                                                      N                    ⁡                                          (                                              v                        ,                        G                                            )                                                        ⁢                  \                  ⁢                  c                                                      ⁢                          R                                                c                  ′                                ⁢                v                                                                        (        4        )            Here N(v, G) denotes the set of neighbors of a node v in graph G and c′εN(v, G), \c refers to the neighbors excluding node c, and Rcv is defined below.
The check node to bit node computation rule is:
                              R          cv                =                              φ                          -              1                                (                                    ∑                                                v                  ′                                ∈                                                      N                    ⁡                                          (                                              c                        ,                        G                                            )                                                        ⁢                  \                  ⁢                  v                                                      ⁢                          φ              ⁡                              (                                  Q                                                            v                      ′                                        ⁢                    c                                                  )                                              )                                    (        5        )            Here,
      φ    ⁡          (      x      )        =      {                  sign        ⁡                  (          x          )                    ,                        -          log                ⁢                                  ⁢                  tanh          ⁡                      (                                                          x                                            2                        )                                }  and operations in the φ-domain are performed over the group {0,1}×R+ (this basically means that the summation here is defined as summation over the magnitudes and XOR over the signs). In a similar manner to equation (4), N(c, G) denotes the set of bit node neighbors of a check node c in graph G, and v′εN(c, G)\v refers to said neighbors excluding node v.
The final decoder estimation for bit ‘v’ is:
                              Q          v                =                              P            v                    +                                    ∑                                                c                  ′                                ∈                                  N                  ⁡                                      (                                          v                      ,                      G                                        )                                                                        ⁢                          R                                                c                  ′                                ⁢                v                                                                        (        6        )            
While properly designed LDPC codes are very powerful (e.g., can correct many errors in a single codeword), a phenomenon known as “trapping sets” may cause the decoder to fail. Failure of the decoder may increase the so-called “error floor” of the decoding algorithm. The term “error floor” refers to the effect whereby, below a certain noise level in the communication channel or in the memory device, the error rate of the output of the decoder starts to decrease much more slowly even though the noise that is responsible for the bit errors becomes smaller.
These trapping sets may cause the decoder to fail, even where the number of incorrect bits may be very small and confined to certain regions of the graph. Trapping sets may be generally thought of as sets with a relatively small number of variable nodes such that the induced sub-graph has only a small number of odd degree check nodes. Trapping sets are a problem in the field of storage since such systems typically require a high degree of reliability, and thus a very small error rate (e.g., fewer than one error for every 1014 bits).
The influence of trapping sets on the onset of error-floors in LDPC codes may be attributed to certain phenomena related to the properties of the code graph and the decoding algorithm used, as well as to realization of certain special channel noise configurations. In the initial stage of BP decoding, variable nodes internal to one particular trapping set (e.g., the so-called “initial trapping set”), experience a large increase in reliability estimates for incorrect bit values due to the presence of special low-probability noise samples. This information may be propagated to other variable nodes in the trapping set, some of which may already have unreliable bit estimates, themselves.
After this initial biasing, external variables may start to correct the initially incorrect estimates. However, the variable nodes in the trapping set may have been biased significantly in their decisions towards the incorrect values due to the influence of the initial trapping set. Since trapping sets may be associated with few check nodes capable of detecting errors within the trapping sets, this erroneous information may persist in the graph until the end of the decoding process.
Furthermore, the unreliable estimates from trapping sets may be amplified or exported to variable nodes external to the trapping set. The degree of influence of the trapping set on the external variables (and vice-versa) may cause further complications in decoding data bits located outside of the trapping set.
One way that others have approached the problem of trapping sets involves reduction of the absolute values of messages in the system, assuming that a larger sum of correct messages will, over time, reverse the error caused by a smaller number of incorrect messages. This may have the effect of preventing the trapping set from “locking” in an incorrect value with high reliability. While this method may reduce the number of decoding errors, it may not always solve the problem. Furthermore, it may degrade decoder performance since additional time may be required for the reduced value messages to converge.